package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 79 单词搜索
 * @date 2024/12/23 16:23
 */
public class E79 {

    /**
     * <h3>方法一：自己想的dfs回溯</h3>
     *
     * @param board 二维字符矩阵
     * @param word  要找的单词
     * @return 找到返回true，否则返回false
     */
    public boolean exist1(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        char[] wordCharArray = word.toCharArray();
        // 以每一个点开始为起点，判断是否能找到
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                // 找到到就返回true
                if (dfs1(board, wordCharArray, new boolean[n][m], 0, i, j))
                    return true;
        // 遍历所有都没找到就返回false
        return false;
    }

    /**
     * dfs回溯实现
     *
     * @param board         二维字符矩阵
     * @param wordCharArray 要找的单词
     * @param visited       访问标记
     * @param k             已经找到的长度
     * @param i             当前点的行坐标
     * @param j             当前点的列坐标
     * @return 是否找到
     */
    private boolean dfs1(
            char[][] board,
            char[] wordCharArray,
            boolean[][] visited,
            int k,
            int i,
            int j) {
        // 1. 已经找到了，返回true
        if (k == wordCharArray.length) {
            return true;
        }
        // 2. 超出边界，返回false
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
            return false;
        }
        // 3. 找到当前位置的字符，并且没有被访问过，并且和要找的单词当前位置的字符相同，则继续递归
        if (!visited[i][j] && board[i][j] == wordCharArray[k]) {
            visited[i][j] = true;
            boolean later = dfs1(board, wordCharArray, visited, k + 1, i - 1, j)
                    || dfs1(board, wordCharArray, visited, k + 1, i, j - 1)
                    || dfs1(board, wordCharArray, visited, k + 1, i + 1, j)
                    || dfs1(board, wordCharArray, visited, k + 1, i, j + 1);
            visited[i][j] = false;
            return later;
        }
        // 4. 否则返回false
        return false;
    }

    // 优化四：优化方向数组
    private static final int[][] DIRECTIONS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    /**
     * <h3>方法二：基于方法一各种优化，效率0ms</h3>
     * @param board 二维字符矩阵
     * @param word 要找的单词
     * @return 找到返回true，否则返回false
     */
    public boolean exist2(char[][] board, String word) {
        // 1. 统计board字符频率
        int[] boardCount = new int[128];
        for (char[] row : board)
            for (char c : row) boardCount[c]++;
        // 2. 统计word字符频率
        char[] wordCharArray = word.toCharArray();
        int[] wordCount = new int[128];
        for (char c : wordCharArray)
            if (++wordCount[c] > boardCount[c])
                return false; // 优化一：board里面的字符都不够，剪枝
        // 优化二：如果word的第一个字符在board中出现次数大于最后一个字符在board中的出现次数，
        // 则反转字符串，因为从少的字符开始找，第一步就可以排除很多的情况，而且字符串反转后也不影响搜索结果
        if (boardCount[wordCharArray[0]] > boardCount[wordCharArray[wordCharArray.length - 1]])
            reverse(wordCharArray);
        // 尝试从每一个单元格开始进行DFS搜索
        int n = board.length, m = board[0].length;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (dfs2(i, j, 0, board, wordCharArray))
                    return true; // 找到
        return false; // 没搜到
    }

    /**
     * 反转字符串
     * @param charArray 字符数组
     */
    private void reverse(char[] charArray) {
        for (int i = 0, j = charArray.length - 1; i < j; i++, j--)
            swap(charArray, i, j);
    }

    /**
     * 交换数组的两个元素
     * @param array 数组
     * @param i 索引i
     * @param j 索引j
     */
    private static void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * dfs回溯搜索
     * @param i 当前行
     * @param j 当前列
     * @param k 当前已经匹配的长度
     * @param board 二维字符矩阵
     * @param word 要搜索的字符串
     * @return 是否找到
     */
    private boolean dfs2(int i, int j, int k, char[][] board, char[] word) {
        // 优化三：提前终止条件
        if (k == word.length - 1 && board[i][j] == word[k])
            return true; // 匹配成功！
        if (board[i][j] != word[k])
            return false; // 匹配失败
        char temp = board[i][j];
        board[i][j] = '#'; // 标记访问过，下次来就匹配不上了
        // 递归搜索相邻的四个方向
        for (int[] d : DIRECTIONS) {
            // 重新计算x、y
            int x = i + d[0];
            int y = j + d[1];
            // 递归搜索
            if (0 <= x && x < board.length // x不能越界
                    && 0 <= y && y < board[x].length // y不能越界
                    && dfs2(x, y, k + 1, board, word)) { // 剩下的部分也递归找到了
                board[i][j] = temp; // 恢复现场
                return true; // 搜到了！
            }
        }
        board[i][j] = temp; // 恢复现场
        return false; // 没搜到
    }
}
